1. Field of the Invention
The invention relates generally to digital circuitry. The invention relates more specifically to an improved method and apparatus for digital multiplication based on shifting of binary-coded data.
2. Description of the Related Art
Use of multiplication is widespread in digital electronic circuits.
The basic AND gate inherently performs a 1-bit by 1-bit, binary-coded multiplication. Larger sized multiplications in which an n-bit wide multiplicand signal (A) is multiplied by an m-bit wide multiplier signal (B) to produce a binary-coded result signal (C=A.multidot.B) that is k-bits wide, where the number of result bits k can be substantially greater than 1, are also ubiquitous. (In most cases, k=m+n. Sometimes the result can be expressed with less than m+n bits through the use of truncation with or without round-off error correction.)
Examples of reliance on digital multiplication may be found in fields such as digital signal processing (DSP) and neural networks. Different proportionality "weights" are routinely assigned in these fields to various parameter signals in order to provide a desired DSP filter function or neural net pattern. Parameter weighting is typically performed by digitally multiplying a parameter signal by a corresponding weight coefficient signal. In the case of real-time adaptive filtering operations and the like, input signals arrive at real-time speed (which can be quite fast). Weighting coefficients may have to change at real-time speed in response to rapidly changing input or other conditions. As a consequence, parameter weighting operations may also need to complete in relatively short time.
Digital multiplication is, of course, also found in the field of general purpose computers. Phrases such as "scaling by a factor", "modulating with another signal" and "attenuating by a factor" are often used in the field of signal processing as equivalents for the operation of generating a result signal that is coded to represent the multiplication of values represented by two or more input signals.
Quite often, one or more of the multiplicand (A), the multiplier (B), and the result signal (C=A.multidot.B) represent a physical quantity such as, but not limited to: (a) X-ray or other tomography measurement signals that are being digitally processed as they are gathered in real time, or after collection, for purposes of improving image quality; (b) heartbeat or other medically-related measurements that are being collected in real time and digitally processed for purposes of providing immediate diagnosis and treatment; (c) audio or ultrasonic signals that are being pre-processed in real-time prior to their production as physical sound waves or that are being post-processed after reception of physical counterparts; (d) video signals that are being pre-processed in real-time prior to production as physical light images or post-processed after reception of physical counterparts; and (e) digital telecommunication signals, such as used in modems and facsimile machines, where the digital telecommunication signals pass through a digital multiplication process as part of a pre-emphasis (modulation) operation or post-emphasis (de-modulation) operation or as part of an error-detection and/or error-correction operation or as part of a data compression or decompression operation.
In many instances, several multiplication operations need to be carried out in a mass-produced circuit. Preferably, such a circuit should be of low cost, compact and composed of one or as small a number of integrated circuit (IC) chips as is economically and technologically practical. It is often desirable to squeeze one or more multiplier circuits onto a single monolithic integrated circuit (IC) chip in a manner which minimizes circuit size, complexity and cost, and gives each IC chip a relatively high level of functionality and performance. Smaller circuit size and simpler circuit topology usually go hand in hand with fewer mass-production defects, increased reliability, reduced power consumption, faster performance, and reduced costs.
Ideally, each on-chip multiplier circuit should be of minimal size so that it can be squeezed economically into the limited space of an IC chip together with like and other functional circuits of the IC. Each on-chip multiplier circuit should also be very fast. It should complete its multiplication operations in minimal time. Moreover, each multiplier circuit should be relatively accurate; meaning that it can produce a correct, or approximately correct, result signal (C=A.multidot.B) even when given an n-bit wide multiplicand signal (A) and m-bit wide multiplier signal (B), where n and m are relatively large numbers.
Unfortunately, conventional approaches to multiplier design fail to attain ideal combinations of these characteristics without making substantial compromises. Multiplication speed and the number of bits handled can be increased through the use of conventional parallel design (e.g., a Wallace tree multiplier), but this tends to increase circuit size dramatically. Large circuit size is undesirable because it leads to decreased mass production yields, reduced per unit reliability, increased per-unit costs and higher levels of power consumption. Circuit size can be minimized through the use of a highly serial design, but then multiplication speed is disadvantageously reduced.